package com.shuo.dsa.sort;

import java.util.Arrays;

/**
 * Created by shuoGG on 2018/9/11
 */
public class ShuoGGInsert {
    public static void main(String[] args) {
        int[] arrays = {9, 8, 1, 4, 2, 3, 5, 6, 7, 13, 12, 14, 11, 15, 16, 17, 19, 18, 10};
        int temp;
        for (int i = 1; i < arrays.length; i++) {
            temp = arrays[i];
            // 左边排好序的数组, 不断往右挪直至找到比array[i]小的值
            while (i >= 1 && arrays[i - 1] > temp) {
                arrays[i] = arrays[i - 1];
                i--;
            }
            arrays[i] = temp;
        }
        System.out.println(Arrays.toString(arrays));
    }

    /**
     * 顺序队列查找返回index,找到直接返回,找不到如[0,1,2,3,5]找4则返回3
     *
     * @param array
     * @param len
     * @param target
     * @return
     */
    private static int orderedSearch(int[] array, int len, int target) {
        if (len == 1) return 0;
        if (len <= 0) throw new RuntimeException("illegal len!!!");
        if (array.length < len) {
            len = array.length;
        }
        for (int i = 0; i < len; i++) {
            if (array[i] == target) return i;
            else if (array[i] > target) return i - 1;
        }
        return array.length - 1;
    }

    /**
     * value插到index位置后面, 最后面塞不进去则舍弃
     *
     * @param array
     * @param index
     * @param value
     */
    private static void insertAfter(int[] array, int index, int value) {
        if (array.length < index) throw new ArrayIndexOutOfBoundsException();
        for (int i = array.length - 1; i > index; i--) {
            array[i] = array[i - 1];
        }
        array[index + 1] = value;
    }

    private static void insertAfter(int[] array, int index, int value, int endIndex) {
        if (array.length < index) throw new ArrayIndexOutOfBoundsException();
        for (int i = endIndex; i > index; i--) {
            array[i] = array[i - 1];
        }
        array[index + 1] = value;
    }
}
